import sys
import bisect
import random
import amara
from amara import binderytools

import pygame

import utils

class PathNode():
	"""
	Used in A* pathfinding.
	"""
	def __init__(self, position, parent):
		self.x, self.y = position
		self.parent = parent
		self.gScore = 0
		self.hScore = 0
		self.fScore = 0
 
	def __lt__(self, other):
		return self.fScore > other.fScore

	def __gt__(self, other):
		return self.fScore < other.fScore

	def __str__(self):
		return "X: %s Y: %s gScore: %s hScore: %s fScore: %s" % (self.x, self.y, self.gScore, self.hScore, self.fScore)

	def tracePath(self, path):
		if self.parent is None:
			return path
		
		path.append((self.x, self.y))
		return self.parent.tracePath(path)

	def neighbors(self, map):
		nodes = []
		
		for position in map.adjacentCells((self.x, self.y)):
			newNode = PathNode(position, self)
			if abs(self.x - position[0]) + abs(self.y - position[1]) > 1:
				newNode.gScore = self.gScore + 14
			else:
				newNode.gScore = self.gScore + 10
				
			nodes.append(newNode)

		return nodes

class Tile:
	def __init__(self, imagePath, cost):
		self.image = utils.load_image(imagePath)
		self.cost = cost

class Map:
	def __init__(self):
		# some default values
		self.width = 0			 
		self.height = 0
		
		self.tileWidth = 0
		self.tileHeight = 0
		self.tiles = {}
		
		self.data = {}

	def __str__(self):
		pass

	def loadMapXML(self, fileName):
		rules= [binderytools.type_inference()]
		document = amara.parse(fileName, rules = rules)

		self.width = document.map.width
		self.height = document.map.height

		self.loadTiles(document)
		self.loadData(document)

	def loadTiles(self, document):
		self.tileWidth = document.map.tileset.tileWidth
		self.tileHeight = document.map.tileset.tileHeight

		for tile in document.map.tileset.tile:
			self.tiles[tile.index] = Tile(str(tile), tile.cost)

	def loadData(self, document):
		x = 0
		y = 0
		nodeData = document.map.data.strip()
		for row in nodeData.splitlines():
			x = 0
			for column in row.strip().split(","):
				self.data[x, y] = int(column)
				x += 1
			y += 1

	def create(self, seed):
		# create random dirt and grass
		for y in range(0, self.height):
			for x in range(0, self.width):
				self.data[x, y] = random.randrange(1, 3)

	def getBlendTile(self, (x, y)):
		returnValue = self.data[x, y]

		# am i dirt?
		if self.data[x, y] == 2:
			if self.inMap((x, y - 1)):
				if self.data[x, y - 1] == 1:
					returnValue = 4

		return returnValue

	def inMap(self, (x, y)):
		return x >= 0 and x < self.width and y >= 0 and y < self.height

	def adjacentCells(self, (x, y)):
		positions = [
				(x - 1, y + 1),
				(x, y + 1),
				(x + 1, y + 1),
				(x - 1, y),
				(x + 1, y),
				(x - 1, y - 1),
				(x, y - 1),
				(x + 1, y - 1)
				]

		i = 0
		while i < len(positions):
			if not self.inMap(positions[i]):
				del positions[i]
				continue
			if self.tiles[self.data[positions[i]]].cost == sys.maxint:
				del positions[i]
				continue
			i += 1

		return positions

	def findPath(self, start, dest):
		"""
		map.findPath() uses the A* algorithm to find the shortest path from start to dest.
		"""
		openList = []
		openHash = {}
		closedHash = {}
		path = []

		# add the starting point
		openList.append(PathNode(start, None))
		openHash[start] = 1

		while len(openList) > 0:
			currentNode = openList.pop()
			del openHash[(currentNode.x, currentNode.y)]
			
			closedHash[(currentNode.x, currentNode.y)] = currentNode
			
			# if we are at the destination return the path
			if currentNode.x == dest[0] and currentNode.y == dest[1]:
				return currentNode.tracePath(path)
		 
			for node in currentNode.neighbors(self):
				if (node.x, node.y) not in closedHash:
					if (node.x, node.y) not in openHash:
						node.hScore = abs(node.x - dest[0]) + abs(node.y - dest[1])
						node.fScore = node.gScore + node.hScore
						bisect.insort(openList, node)
						openHash[(node.x, node.y)] = 1

